import java.util.*;

public class Test {
    /*
    题目 1：和为 s 的两个数字
     */
    public int[] twoSum(int[] nums, int target) {
        int n = nums.length;

        int left = 0;
        int right = n - 1;

        int[] arr = new int[2];

        while(left < right){
            int sum = nums[left] + nums[right];
            if(sum > target){
                right--;
            }else if(sum < target){
                left++;
            }else{
                arr[0] = nums[left];
                arr[1] = nums[right];
                return arr;
            }
        }

        return arr;
    }

    /*
    题目 2: 三数之和
     */
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);

        List<List<Integer>> lists = new LinkedList<>();
        int n = nums.length;


        for(int i = 0; i < n - 2;){
            int tg = -nums[i];
            int left = i + 1;
            int right = n - 1;

            while(left < right){
                int sum = nums[left] + nums[right];
                if(sum > tg){
                    right--;
                }else if(sum < tg){
                    left++;
                }else{
                    List<Integer> list = new LinkedList<>();
                    list.add(nums[i]);
                    list.add(nums[left]);
                    list.add(nums[right]);
                    lists.add(list);

                    left++;
                    right--;

                    // 跳过重复的！
                    while(left < right && nums[left] == nums[left - 1]){
                        left++;
                    }

                    while(left < right && nums[right] == nums[right + 1]){
                        right--;
                    }
                }
            }

            i++;
            while(i < n - 2 && nums[i] == nums[i - 1]){
                i++;
            }
        }

        return lists;
    }

    /*
    题目 3：四数之和
     */
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        int n = nums.length;
        List<List<Integer>> lists = new LinkedList<>();

        for(int i = 0; i < n - 3; ){
            for(int j = i + 1; j < n - 2;){
                long tg = (long)target - nums[i] - nums[j];
                int left = j + 1;
                int right = n - 1;

                while(left < right){
                    int sum = nums[left] + nums[right];

                    if(sum > tg){
                        right--;
                    }else if(sum < tg){
                        left++;
                    }else{
                        List<Integer> list = new LinkedList<>();
                        list.add(nums[i]);
                        list.add(nums[j]);
                        list.add(nums[left]);
                        list.add(nums[right]);
                        lists.add(list);

                        left++;
                        right--;

                        while(left < right && nums[left] == nums[left - 1]){
                            left++;
                        }

                        while(left < right && nums[right] == nums[right + 1]){
                            right--;
                        }
                    }
                }
                j++;
                while(j < n - 2 && nums[j] == nums[j - 1]){
                    j++;
                }
            }
            i++;
            while(i < n - 3 && nums[i] == nums[i - 1]){
                i++;
            }
        }
        return lists;
    }

    /*
    移动窗口专题：
     */
    /*
    题目 4：长度最小的子数组
     */
    public int minSubArrayLen(int target, int[] nums) {

        int n = nums.length;
        int len = n + 1;
        int sum = 0;

        for(int left = 0, right = 0; right < n; right++){
            sum += nums[right];

            while(sum >= target){
                len = Math.min(len, right - left + 1);
                sum -= nums[left++];
            }
        }
        return len == n + 1 ? 0 : len;
    }

    /*
    题目 5 ：无重复字符的最长子串
     */
    public int lengthOfLongestSubstring(String ss) {
        int[] hash = new int[128]; // 使用 数组来模拟哈希表！

        char[] s = ss.toCharArray();

        int n = s.length;
        int len = 0;

        for(int left = 0, right = 0; right < n; right++){
            // 1. 入窗口
            hash[s[right]]++;

            // 2. 判断
            while(hash[s[right]] > 1){
                // 3. 出窗口
                hash[s[left++]]--;
            }

            len = Math.max(len, right - left + 1);
        }
        return len;
    }

    /*
    题目 6：最大连续 1 的个数Ⅲ
     */
    // 最大连续 1 的个数 这个问题可以转换成
    // 找出最长的子数组，0 的个数不超过 k 个！
    public int longestOnes(int[] nums, int k) {
        int n = nums.length;
        int len = 0;
        int zero = 0;

        for(int left = 0, right = 0; right < n; right++){
            if(nums[right] == 0) zero++;

            while(zero > k){
                if(nums[left++] == 0) zero--;
            }

            len = Math.max(len, right - left + 1);
        }

        return len;
    }

    /*
    题目 7：将 x 减到 0 的最小操作数
     */
    // 该题转换成：找出最长的子数组的长度，所有元素的和正好等于 sum - x
    public static int minOperations1(int[] nums, int x) {
        int n = nums.length;
        int len = 0;
        int sum = 0;
        int s = 0;

        for(int y : nums){
            s += y;
        }

        int tg = s - x;
        if(tg < 0) return -1;
        if(tg == 0) return n;

        for(int left = 0, right = 0; right < n; right++){
            sum += nums[right];

            while(sum >= tg){

                if(sum == tg){
                    len = Math.max(len, right - left + 1);
                }
                sum -= nums[left++];

            }
        }
        return len == 0 ? -1 : n - len;
    }

    public int minOperations(int[] nums, int x) {
        int n = nums.length;
        int sum = 0;
        for(int y : nums){
            sum += y;
        }

        int tg = sum - x;
        if(tg < 0) return -1;

        int s = 0;
        int len = -1;

        for(int left = 0, right = 0; right < n; right++){
            s += nums[right];

            while(s > tg){
                s -= nums[left++];
            }

            if(s == tg){
                len = Math.max(len, right - left + 1);
            }
        }

        return len == -1 ? len : n - len;
    }

    /*
    题目 8：水果篮子
     */
    public int totalFruit(int[] f) {
        int n = f.length;
        int len = 0;
        Map<Integer, Integer> map = new HashMap<>();

        for(int left = 0, right = 0; right < n; right++){
            int in = f[right];
            map.put(in, map.getOrDefault(in, 0) + 1);

            while(map.size() > 2){
                int out = f[left];
                map.put(out, map.get(out) - 1);

                if(map.get(out) == 0){
                    map.remove(out);
                }
                left++;
            }

            len = Math.max(len, right - left + 1);
        }
        return len;
    }

}
